1884B - Haunted House - CodeForces Solution


greedy math two pointers

Please click on ads to support us..

C++ Code:

#include <bits/stdc++.h>
using namespace std;
int solve(int t,string str){

}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        string str;
        cin>>n>>str;
        int n0=0;
        queue<long long> s1;
        for(int i=n-1;i>=0;i--){
            if(str[i]=='0'){
                n0++;
                s1.push(i);
            }
        }
        long long ans=0;
        for(int i=1;i<=n0;i++){
            int idx=n-i;
            ans+=idx-s1.front();
            cout<<ans<<" ";
            s1.pop();
        }
        for(int i=n0+1;i<=n;i++){
            cout<<"-1 ";
        }
        cout<<endl;
    }
}


Comments

Submit
0 Comments
More Questions

489A - SwapSort
932A - Palindromic Supersequence
433A - Kitahara Haruki's Gift
672A - Summer Camp
1277A - Happy Birthday Polycarp
577A - Multiplication Table
817C - Really Big Numbers
1355A - Sequence with Digits
977B - Two-gram
993A - Two Squares
1659D - Reverse Sort Sum
1659A - Red Versus Blue
1659B - Bit Flipping
1480B - The Great Hero
1519B - The Cake Is a Lie
1659C - Line Empire
515A - Drazil and Date
1084B - Kvass and the Fair Nut
1101A - Minimum Integer
985D - Sand Fortress
1279A - New Year Garland
1279B - Verse For Santa
202A - LLPS
978A - Remove Duplicates
1304A - Two Rabbits
225A - Dice Tower
1660D - Maximum Product Strikes Back
1513A - Array and Peaks
1251B - Binary Palindromes
768B - Code For 1